/*
 * (C) 2012	Sheng Yi
 * Find out two integers that appearance just once in an array
 * while other integers appearance twice.
 */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

struct once_int
{
	int one;
	int another;
};

struct once_int find_once(int array[], int len);
int lowest_bit(int key);

int main()
{
	struct once_int oi;
	int array[10] = { 1, 1, 2, 3, 4, 3, 2, 4, 8, 6};
	oi = find_once(array, 10);
	printf("{%d %d}\n", oi.one, oi.another);

	/*
	int array1[10] = { 1, 1, 2, 3, 4, 3, 2, 4, 8, 6};
	oi = find_once(array1, 0);
	printf("{%d %d}\n", oi.one, oi.another);
	*/

	/*
	int array2[10] = { 1, 1, -2, 3, 4, 3, -2, 4, 8, 6};
	oi = find_once(array2, 10);
	printf("{%d %d}\n", oi.one, oi.another);
	*/
	return 0;
}

struct once_int find_once(int array[], int len)
{
	assert(len > 0);
	struct once_int oi;
	int i, pos, key = 0;
	for (i = 0; i < len; i++)
		key ^= array[i];	// XOR is difference between two integers. Two same integers XOR get 0, any integer XOR 0 keeps itself

	assert(key > 0);
	// now KEY is the difference between the two once appearanceed integer
	// use KEY to make all integers two groups, each group contains one integer that appearanceed once
	pos = lowest_bit(key);	// POS must bigger than 0
	assert(pos >= 0);

	pos = 1 << pos;
	oi.one = 0;
	oi.another = 0;
	for (i = 0; i < len; i++)
	{
		assert(array[i] >= 0);
		if (array[i] & pos)	// integer that the POSth bit is 1
			oi.one ^= array[i];
		else	// integer that the POSth bit is 0
			oi.another ^= array[i];
	}

	return oi;
}

int lowest_bit(int key)
{
	int pos = 0, i = 0;
	while (key && !((key >> i++) & 0x01))
		pos += 1;
	return pos;
}
